package org.example;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Test4 {
    //leetcode 93 复原IP地址 https://leetcode.cn/problems/restore-ip-addresses/description/
    /**
     * 方法一：通过list来存储结果，最后将list中的元素通过.连接成为字符串
     */
    public List<String> ret;
    public List<String> list;
    public List<String> restoreIpAddresses1(String s) {
        ret = new ArrayList<>();
        list = new ArrayList<>();
        if (s.length() > 12) return ret;
        backtracking1(s,0);
        return ret;
    }

    public void backtracking1(String s,int start) {
        if (start >= s.length()) {
            if (list.size() == 4) {
                ret.add(list.stream().collect(Collectors.joining(".")));
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String tmp = s.substring(start, i + 1);
            if (isRight(tmp)) {
                list.add(tmp);
            }else {
                break;
            }
            backtracking1(s,i + 1);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 方法二：通过StrngBuilder来解决，速度更快
     */
    public int length;
    public List<String> restoreIpAddresses(String s) {
        ret = new ArrayList<>();
        length = s.length();
        if (s.length() > 12) return ret;
        backtracking(new StringBuilder(s),0);
        return ret;
    }

    public void backtracking(StringBuilder s,int start) {
        if (s.length() == length + 3) {
            if (isRight(s.substring(start,s.length()))) {
                ret.add(s.toString());
            }
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String tmp = s.substring(start, i + 1);
            if (isRight(tmp)) {
                s.insert(i + 1,'.');
            }else {
                break;
            }
            backtracking(s,i + 2);
            s.deleteCharAt(i + 1);
        }
    }

    private boolean isRight(String s) {
        if (s == null || s.equals("")) return false;
        if (s.charAt(0) == '0' && s.length() > 1) {
            return false;
        }
        int num = Integer.valueOf(s);
        if (num > 255) return false;
        return true;
    }

    public static void main(String[] args) {
        Test4 test4 = new Test4();
        test4.restoreIpAddresses("101023");
        System.out.println(4444);
    }
}
